# 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“
# 房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。 
# 
#  计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。 
# 
#  示例 1: 
# 
#  输入: [3,2,3,null,3,null,1]
# 
#      3
#     / \
#    2   3
#     \   \ 
#      3   1
# 
# 输出: 7 
# 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7. 
# 
#  示例 2: 
# 
#  输入: [3,4,5,1,3,null,1]
# 
#      3
#     / \
#    4   5
#   / \   \ 
#  1   3   1
# 
# 输出: 9
# 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
#  
#  Related Topics 树 深度优先搜索 
#  👍 569 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    map = {}

    def rob(self, root: TreeNode) -> int:
        """
        和列表不同。这里的思路是 递归，每当遇到个节点时候，可以决定偷或者不偷，同时需要知道，该节点的父节点是否被偷过，被偷过
        那么不能再偷了，继续深度递归下去，同时记录当前金额，最后取出最大值
        如果没有偷过：
        可以决定偷还是不偷
        :param root:
        :return:
        """
        if not root:
            return 0

        if self.map.get(root):
            return self.map[root]

        profit, profit1 = root.val, 0

        if root.left:
            profit += self.rob(root.left.left) + self.rob(root.left.right)
            profit1 += self.rob(root.left)

        if root.right:
            profit += self.rob(root.right.left) + self.rob(root.right.right)
            profit1 += self.rob(root.right)
        res = max(profit1, profit)
        self.map[root] = res
        return res
    # leetcode submit region end(Prohibit modification and deletion)
